package com.carl.leetcode.pointer;

import java.util.Arrays;

/**
 * Created by carlXie on 2016/1/19.
 * email: kkrimen@gmail.com
 */
public class ThreeSumClosest {
    public static void main(String[] args) {
        int[] nums = new int[]{13,2,0,-14,-20,19,8,-5,-13,-3,20,15,20,5,13,14,-17,-7,12,-6,0,20,-19,-1,-15,-2,8,-2,-9,13,0,-3,-18,-9,-9,-19,17,-14,-19,-4,-16,2,0,9,5,-7,-4,20,18,9,0,12,-1,10,-17,-11,16,-13,-14,-3,0,2,-18,2,8,20,-15,3,-13,-12,-2,-19,11,11,-10,1,1,-10,-2,12,0,17,-19,-7,8,-19,-17,5,-5,-10,8,0,-12,4,19,2,0,12,14,-9,15,7,0,-16,-5,16,-12,0,2,-16,14,18,12,13,5,0,5,6};
        System.out.println(threeSumClosest(nums, -59));
    }

    public static int threeSumClosest(int[] nums, int target) {
        if(nums.length < 3) return 0;

        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int front = i + 1;
            int rear = nums.length - 1;

            while(front < rear) {
                int delta = target - (nums[i] + nums[front] + nums[rear]);
                if(delta == 0) {
                    return target;
                } else {
                    min = Math.abs(delta) > Math.abs(min) ? min : delta;
                    if(front < rear && delta > 0) ++ front;
                    if(front < rear && delta < 0) -- rear;
                }
            }
        }
        return target - min;
    }
}
